package com.breeze.sort;

/**
 * 快速排序-分治思想(D&C)
 * 分治思想：将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同
 * 分治算法步骤：1. 分解 2.用简单的方法对分解的问题求解 3.合并
 * 快速排序：
 * 1. 分解：将整个排序问题分解为选出基准值，使左小右大的问题，对基准值的左右侧分别采用该方法，最终整个序列又会有序
 * 2. 求解：找出基准值，使左小右大
 * 3. 合并：递归调用求解思想，最终数组即有序
 */
public class QuickSort implements Sort {
    @Override
    public void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private void sort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivotIndex = partition(arr, left, right);
        sort(arr, left, pivotIndex - 1);
        sort(arr, pivotIndex + 1, right);
    }

    /**
     * 返回基准值下标，保证基准值左小右大
     */
    private int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        while (left < right) {
            while (arr[right] >= pivot && left < right) {
                right--;
            }
            arr[left] = arr[right];
            while (arr[left] <= pivot && left < right) {
                left++;
            }
            arr[right] = arr[left];
        }
        // 退出循环时，left == right,这个位置就是基准元素最终的位置
        arr[left] = pivot;
        return left;
    }
}
